Reason maintainance/Maintien du raisonnement in areas (2024-03-15)

Non monotonic reason maintenance systems (RMS) are able, provided with a dependency graph (which represents a reasoning), to return a weakly grounded labelling of that graph (which represents a set of beliefs that the reasoner can hold). There can be several weakly grounded labellings. This work investigates the labelling process of these graphs in order to find parts of the graph which lead to multiple labellings: the multiple labelling generators (MLG). Two criteria are presented in order to isolate them. It is proved that:

• they do not belong to stratified even strongly connected components (SCC) of the complete support graph.
• they are successive initial SCC of unlabelled part of alternate even SCC.

Previous algorithms from Doyle and Goodwin are considered and new ones are put forward. This leads to a better understanding of labelling generation mechanisms and previous algorithms. They are discussed from the stand-point of the properties of correctness and potential completeness (the ability to find one but any of the labellings).

ELSA is an application concerning avalanche path analysis which takes advantages of a reason maintenance system. In order to fully describe it, the tool on which the ELSA application is developed - Shirka/TMS - is first described. It is noteworthy that the RMS on Shirka is a special one. It is only used for cache consistency maintenance. As a consequence, the importance of Shirka/TMS in ELSA is in preserving cache consistency rather than defaults assumptions and backtracking. Then, the processing of the ELSA system is presented, emphasizing on the use of the RMS: the RMS of Shirka is critical for the performances of the whole system. This is illustrated in the third part in which are given some comparison of the use of ELSA with and without its RMS, in order to highlight the advantages of such a device.

Le modèle d'exploration d'un espace de recherche utilisé par Pecos est le retour-arrière chronologique. Il consiste, lorsque l'on a détecté une inconsistance (le domaine d'une variable est vide), à revenir au dernier point de choix pour explorer les autres alternatives. Ce modèle d'exploration ne conserve pas les véritables raisons de l'inconsistance. La question que l'on se pose est celle d'exploiter ces dépendances afin d'explorer un nombre minimum d'alternatives dans tout le graphe.

Some knowledge based systems will have to deal with increasing amount of knowledge. In order to avoid memory overflow, it is necessary to clean memory of useless data. Here is a first step toward an intelligent automatic forgetting scheme. The problem of the close relation between forgetting and inferring is addressed, and a general solution is proposed. It is implemented as invalidation operators for reasoning maintenance system dependency graphs. This results in a general architecture for selective forgetting which is presented in the framework of the Sachem system.

A new kind of RMS, based on a close merge of TMS and ATMS, is proposed. It uses the TMS graph and interpretation and the ATMS multiple context labelling procedure. In order to fill in the problems of the ATMS environments in presence of nonmonotonic inferences, a new kind of environment, able to take into account hypotheses that do not hold, is defined. These environments can inherit formulas that hold as in the ATMS context lattice. The dependency graph can be interpreted with regard to these environments; so every node can be labelled. Furthermore, this leads to consider several possible interpretations of a query.

SaMaRis est un logiciel destiné à l'étude et à l'expérimentation des systèmes de maintien du raisonnement, ou de tout autre type de systèmes tirant parti d'une représentation explicite d'un raisonnement afin de lui faire subir des opérations constructives (rétablissement de la cohérence), destructives (oubli) ou consultatives (explication). Son architecture est composée de quatre modules indépendants: le protocole de communication avec le système d'inférence, le graphe de dépendances représentant le raisonnement lui-même, les services associés au graphe et les applications générales sur ce graphe. SaMaRis n'a aucune connaissance de la sémantique associée au graphe par le système d'inférence, ainsi son action peut-elle être adaptée à divers types de raisonnements.

For reasoning systems, it is sometime useful to cache away the inferred values. Meanwhile, when the system works in a dynamic environment, cache coherence has to be performed, and this can be achieved with the help of a reasoning maintenance system (RMS). The questions to be answered, before implementing such a system for a particular application, are: how much is caching useful ? Does the system need a dynamicity management system ? Is a RMS suited (what will be its overhead) ?
We provide an application driven evaluation framework in order to answer these questions. The evaluation is based on the real work to be processed on the reasoning of the application. First, we express the action of caching and maintaining with two concepts: backward and forward cone effects. Then we quantify the inference time for those systems and find the quantification of the cone effects in the formulas.

For reasoning systems, it is sometime useful to cache away the inferred values. Meanwhile, when the system works in a dynamic environment, cache coherence has to be performed, and this can be achieved with the help of a reasoning maintenance system (RMS). The questions to be answered, before implementing such a system for a particular application, are: how much is caching useful ? Does the system need a dynamicity management system ? Is a RMS suited (what will be its overhead) ?
We provide an application driven evaluation framework in order to answer these questions. The evaluation is not based on the intrinsic complexity of RMS but on the real work to be processed on the reasoning of the application. First, we express the action of caching and maintaining with two concepts: backward and forward cone effects. Then we quantify the inference time for those systems and find the quantification of the cone effects in the formulas.
As a consequence, the decision to use caching and/or RMS is expressed as a tradeoff between the advantages and disadvantages of both cone effects.

We propose a model of "agent" that has some characteristics at the crossroad of several ongoing research tracks: self rationality, autoepistemic reasoning, cooperative agents and resource-bounded reasoning. That model is particular since available technologies enable its implementation and thus its experimentation. Although in distributed artificial intelligence, the emphasis is on cooperation, we concentrate on belief management. We stress here the resource-bounded reasoning aspect of the work but describe first the architecture of our agents. We then describe the kind of behavior we expect from forgetting and show that this is achievable in both the theoretical and practical frameworks.

Le raisonnement hypothétique consiste à compléter la connaissance disponible afin de poursuivre un raisonnement. L'aide aux utilisateurs de systèmes de raisonnement hypothétique nécessite la conception d'algorithmes spécifiques, pour pouvoir gérer efficacement les hypothèses et leurs conséquences et pour permettre de poser automatiquement des hypothèses. Cette dernière exigence conduit à implémenter un raisonnement non monotone. Les systèmes de maintenance de la vérité enregistrent les inférences produites par un système de raisonnement sous forme d'un graphe de dépendances et se chargent de garantir la cohérence des formules présentes dans une base de connaissance. Deux types de systèmes de maintenance de la vérité ont été proposés: (i) Les systèmes à propagation acceptent des inférences non monotones et propagent la validité absolue au sein du graphe de dépendances. L'étiquetage obtenu représente une interprétation du graphe. (ii) Les systèmes à contextes n'acceptent que des inférences monotones mais propagent des étiquettes dénotant les contextes dans lesquels les formules doivent être présentes. Ils permettent donc de raisonner sous plusieurs contextes simultanément. Le but de ce travail est de concevoir un système qui combine leurs avantages. Il permet de raisonner simultanément sous plusieurs contextes à l'aide d'inférences non monotones. Pour cela, des environnements capables de tenir compte de l'absence d'hypothèses sont définis. Une interprétation est associée à ces environnements et est étendue aux noeuds du graphe de dépendances, en accord avec l'interprétation des systèmes à propagation. Cela permet d'établir la signification des étiquettes associées aux noeuds du graphe, et de proposer de multiples possibilités de soumettre des requêtes au système. Un système correspondant à cette caractérisation, le CP-TMS, est implémenté comme une extension des systèmes de maintenance de la vérité à propagation. Cette implémentation est décrite ici, puis critiquée.

Les systèmes de maintenance de la vérité ont été conçus pour raisonner à l'aide de connaissance incomplète. Un système de maintenance de la vérité qui combine les avantages des TMS - autorisant l'utilisation d'inférences non monotones - et des ATMS - considérant le raisonnement sous plusieurs contextes simultanément - est présenté. Il maintient un graphe de dépendances entre les objets utilisés par un système de raisonnement et propage à travers ce graphe les contextes dans lesquels les noeuds sont valides. Une théorie de l'interprétation des contextes est présentée. Elle garantit certaines bonnes propriétés aux contextes manipulés par l'implémentation. Les réponses aux requêtes peuvent alors être interprétées sur la base théorique ainsi posée.

Les systèmes de maintenance de la vérité ont été conçus pour raisonner à l'aide de connaissance incomplète. Le CP-TMS est un système de maintenance de la vérité tentant de combiner les avantages des systèmes à propagation (TMS) - autorisant l'utilisation d'inférences non monotones - et des systèmes à contextes (ATMS) - considérant le raisonnement sous plusieurs contextes simultanément. Il maintient un graphe de dépendances entre les objets manipulés par un système de raisonnement et propage à travers ce graphe les contextes dans lesquels les noeuds sont valides. Ces contextes prennent en compte l'incomplétude des bases de connaissance et permettent d'exprimer des inférences non monotones. Une théorie de l'interprétation des contextes est présentée. Elle garantit certaines bonnes propriétés aux contextes manipulés par l'implémentation. Le système garantit la consistance des contextes manipulés et permet de répondre à des requêtes concernant différents contextes simultanément au regard de la base théorique ainsi posée.

After a review of the different ways to consider nonmonotonicity problems arising in knowledge bases as an extension of incompleteness problems in databases, this report will expose in details the implementation of a TMS as a cache consistency maintenance system as it was proposed in the previous report. The problems which stem from this implementation are discussed together with some solutions; they are the integrity constraint satisfaction problem and the secondary storage strategies to consider.

Ce rapport présente d'abord le fonctionnement général des systèmes de maintenance de la vérité. À partir de l'analyse détaillée des algorithmes proposés antérieurement, un nouvel algorithme reposant essentiellement sur la notion de noeuds influants, sur la validité d'une composante fortement connexe du graphe de dépendances, est décrit. Une critique de cet algorithme est finalement présentée.

On présente ici un module de l'AGC qui est un système de maintenance de la vérité conçu pour être interfaçable avec différents mécanismes d'inférence. Après une brève présentation des systèmes de maintenance de la vérité, celui qui est proposé est approfondi au travers d'un exemple avant que ne soient abordés les problèmes d'interfaçages proprement dit. Le guide d'interfaçage décrit deux types de liaisons: une liaison de bas niveau et une liaison de haut niveau. En annexe figure la liste des fichiers fournis avec le module ainsi que les fonctions qu'ils contienent, puis un ensemble de tests permettant d'aborder les point cruciaux de l'interface.

Après avoir défini le terme de base de connaissance, utilisé à la fois par les champs de recherche en l'intelligence artificielle et des bases de données, ce papier présente des réflexions et des travaux sur le thème de l'intégration d'un système de maintien des croyances dans une base de connaissance. Dans la perspective de grandes bases de connaissance - à la fois par la taille et par la durée de vie - la nécessité d'un mécanisme capable de garantir la validité du contenu de la base par rapport à un ensemble d'inférences semble inéluctable. Les systèmes de maintien des croyances développés pour les systèmes à base de règles sont candidats pour assurer cette tâche. Leur adaptation aux bases de connaissance, et en particulier au modèle centré-objet, est présentée au travers du système de représentation de connaissance Shirka.

Le raisonnement non monotone est souvent une conséquence de la connexion des systèmes à base de connaissance à des systèmes informatiques extérieurs. Ces derniers sont en effet susceptibles d'agir sur les données et les connaissances de la base. Les systèmes de maintenance de la vérité (truth maintenance systems) possèdent certaines fonctionnalités requises pour gérer la non monotonie. Ils sont évalués dans le contexte d'une utilisation des représentations centrées-objet. Les caractéristiques de ces dernières (héritage, attachement procédural, valeurs par défaut, attributs multi-valués), et en particulier du modèle retenu dans le système Shirka, amènent à des solutions spécifiques.

L'utilisation d'objets pour la représentation des connaissances est de plus en plus répandue. C'est dire l'importance que prend la conception de bases de connaissance centrées-objet qui peuvent être manipulés de manière non monotone par divers systèmes informatiques tant pour y opérer des modifications que des consultations.
On se propose d'étudier des mécanismes permettant à la fois plus d'efficacité et de cohérence dans l'utilisation d'une représentation centrée-objet. Le mécanisme de caching introduit des problèmes liés à l'utilisation non monotone de la base. Dans le but de palier ces problèmes, les différents systèmes de maintenance de la vérité existant sont étudiés.
Un cadre général permettant la coopération des mécanismes de "caching" et de maintenance de la vérité au sein d'une représentation centrée-objet est proposé. On présente ensuite une réalisation effective des propositions sur le système de gestion de bases de connaissance centrées-objet Shirka.